1.两数之和 easy

Link

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

题解思路1 暴力枚举

暴力解法，两层循环遍历数组，找到和为目标值的两个数。

javascript

var twoSum = function(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

go

func twoSum(nums []int, target int) []int {
  for i := 0; i < len(nums); i++ {
    for j := i + 1; j < len(nums); j++ {
      if nums[i] + nums[j] == target {
        return []int{i, j}
      }
    }
  }
  return nil
}

题解思路2 哈希表

使用哈希表存储数组元素和索引的映射关系，遍历数组，查找哈希表中是否存在目标值与当前元素的差值。

javascript

var twoSum = function(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
};

go

func twoSum(nums []int, target int) []int {
  m := make(map[int]int)
  for i, v := range nums {
    if j, ok := m[target-v]; ok {
      return []int{j, i}
    }
    m[v] = i
  }
  return nil
}

2.两数相加 medium

Link

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

题解思路1 模拟

模拟手工计算两个数相加的过程，使用变量记录进位。

javascript

var addTwoNumbers = function (l1, l2) {
    const r = new ListNode(0)
    let carry = 0, curr = r;
    while (l1 !== null || l2 !== null) {
        let x = 0, y = 0;
        if (l1 !== null) {
            x = l1.val
            l1 = l1.next
        }
        if (l2 !== null) {
            y = l2.val
            l2 = l2.next
        }
        const s = x + y + carry
        carry = Math.floor(s / 10)
        curr.next = new ListNode(s % 10)
        curr = curr.next
    }
    if (carry > 0) {
        curr.next = new ListNode(carry)
    }
    return r.next
};

go

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
  dummy := &ListNode{}
  p, q, curr := l1, l2, dummy
  carry := 0
  for p != nil || q != nil {
    x := 0
    if p != nil {
      x = p.Val
      p = p.Next
    }
    y := 0
    if q != nil {
      y = q.Val
      q = q.Next
    }
    sum := carry + x + y
    carry = sum / 10
    curr.Next = &ListNode{Val: sum % 10}
    curr = curr.Next
  }
  if carry > 0 {
    curr.Next = &ListNode{Val: carry}
  }
  return dummy.Next
}

题解思路2 递归

递归计算两个链表的和，递归终止条件是两个链表都为空，递归过程中计算当前节点的和并递归计算下一个节点的和。

var addTwoNumbers = function (l1, l2) {
    return add(l1, l2, 0)
};

function add(l1, l2, carry) {
    if (l1 === null && l2 === null) {
        return carry > 0 ? new ListNode(carry) : null
    }
    if (l1 === null) {
        l1 = new ListNode(0)
    }
    if (l2 === null) {
        l2 = new ListNode(0)
    }
    const sum = l1.val + l2.val + carry
    const node = new ListNode(sum % 10)
    node.next = add(l1.next, l2.next, Math.floor(sum / 10))
    return node
}

3.无重复字符的最长子串 medium

Link

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

题解思路1 滑动窗口

使用滑动窗口维护一个不含重复字符的子串，遍历字符串，使用哈希表存储字符的索引，当遇到重复字符时，更新滑动窗口的左边界。

js code 1 map

var lengthOfLongestSubstring = function(s) {
  const map = new Map();
  let max = 0, left = 0;
  for (let i = 0; i < s.length; i++) {
    // 如果map中有s[i]，则更新左边界
    if (map.has(s[i])) {
      // 更新左边界  (考虑 abcb 这种情况 这里直接 letf = 1，无需像set那样一个一个删除) 
      left = Math.max(left, map.get(s[i]) + 1);
    }
    // 更新map s[i]的索引 i
    map.set(s[i], i);
    // 更新最大长度
    max = Math.max(max, i - left + 1);
  }
  return max;
};

js code 2 set

/**
 * 在遇到重复字符时，需要通过移动窗口的起始位置（start指针）并逐一从Set中删除元素，
 * 直到删除了重复的字符。这个过程可能相对较慢，尤其是当窗口大小变得很大时。
 */
var lengthOfLongestSubstring = function (s) {
    if (!s) return 0
    let start = 0, end = 0;
    let set = new Set()
    set.add(s[start])
    // s.length = 1 时 max默认为1
    let max = 1
    while (end < s.length) {
        // end 在边界内走一步
        end++
        // 处理越界
        if (end >= s.length) {
            break
        }
        // 判断新的s[end]是否在s[start,end]里面重复 
        while (set.has(s[end]) && start < end) {
            // 移除重复
            set.delete(s[start])
            // 前进
            start++
        }
        // 将新元素加入
        set.add(s[end])
        max = Math.max(max, end - start + 1, 1)
    }
    return max
};

4.寻找两个正序数组的中位数 hard

Link

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

题解思路1 合并数组-归并排序

将两个数组合并成一个数组，然后找到中位数。

javascript

var findMedianSortedArrays = function(nums1, nums2) {
    let i = 0, j = 0;
    const n = nums1.length, m = nums2.length;
    // 合并后的数组
    const nums = [];
    while (i < n || j < m) {
        // 如果nums1遍历完了，将nums2剩余的元素加入nums
        if (i === n) {
            nums.push(nums2[j++]);
        // 如果nums2遍历完了，将nums1剩余的元素加入nums
        } else if (j === m) {
            nums.push(nums1[i++]);
        // 如果nums1[i] < nums2[j]，将nums1[i]加入nums    
        } else if (nums1[i] < nums2[j]) {
            nums.push(nums1[i++]);
        // 如果nums1[i] >= nums2[j]，将nums2[j]加入nums
        } else {
            nums.push(nums2[j++]);
        }
    }
    // 如果合并后的数组长度为偶数，返回中间两个数的平均值
    const len = n + m;
    if (len % 2 === 0) {
        return (nums[len / 2 - 1] + nums[len / 2]) / 2;
    // 如果合并后的数组长度为奇数，返回中间的数
    } else {
        return nums[(len - 1) / 2];
    }
};

题解思路2 第k小数

寻找两个有序数组的中位数，可以转化为寻找两个有序数组中的第 k 小数。

javascript

题解思路3 二分查找 有序数组划分

javascript

5.最长回文子串 medium

Link

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

题解思路1 中心扩展

遍历字符串，以当前字符为中心，向两边扩展，找到最长的回文子串。

javascript

    const length = s.length
    let maxStr = ''
    for (let i = 0; i < length; i++) {
        let left = i - 1
        let right = i + 1
        let curr = s[i]
        // 从中心向两边扩展
        
        // 先向左边扩展 直到不是回文串
        while (left >= 0 && s[i] === s[left]) {
            curr = s[left] + curr
            left--
        }
        // 再向右边扩展 直到不是回文串
        while (right < length && s[i] === s[right]) {
            curr = curr + s[right]
            right++
        }
        // 向两边扩展 直到不是回文串
        while (s[left] === s[right] && left >= 0 && right < length) {
            curr = s[left] + curr + s[right]
            left--
            right++
        }
        if (maxStr.length < curr.length) {
            maxStr = curr
        }
    }
    return maxStr

算法复杂度为O(n^2)，空间复杂度为O(1)。

题解思路2 动态规划

使用动态规划求解最长回文子串, dp[i][j] 表示 s[i:j] 是否是回文串。

我们可以得到状态转移方程： dp[i][j] = (s[i] === s[j]) && dp[i + 1][j - 1]。 如果 s[i] === s[j]，且 s[i + 1:j - 1] 是回文串，则 s[i:j] 也是回文串。

javascript

var longestPalindrome = function(s) {
    const n = s.length;
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(false));
    let ans = '';
    for (let len = 0; len < n; ++len) {
        for (let i = 0; i + len < n; ++i) {
            let j = i + len;
            if(j >= n) {
                break;
            }
            if (len === 0) {
                dp[i][j] = true;
            } else if (len === 1) {
                dp[i][j] = s[i] === s[j];
            } else {
                dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
            }
            if (dp[i][j] && len + 1 > ans.length) {
                ans = s.substring(i, i + len + 1);
            }
        }
    }
    return ans;
};

export default function App(): JSX.Element {
  return <h1>Hello world</h1>
}

Open Sandbox

缺点：时间复杂度为O(n^2)，空间复杂度为O(n^2)。

6.Z 字形变换 medium

Link

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
    // 如果只有一行，直接返回s
    if (numRows === 1) {
        return s;
    }
    // 声明一个数组，数组的长度为numRows 用于存储每一行的字符
    const memo = [];
    for (let i = 0; i < numRows; i++) {
        memo.push([]);
    }
    // 当前行
    let curr = 0;
    // 模式 递增或者递减
    let mode = 'increase';
    for (let j = 0; j < s.length; j++) {
        // 当前字符
        const sc = s[j];
        // 将当前字符加入memo[curr]中
        memo[curr].push(sc);
        if (mode === 'increase') {
            // 当curr到达numRows - 1时，切换模式 例如 numRows = 3 时，curr 0 1 2 1 0 1 2 1 0 ...
            curr++;
            if (curr >= numRows - 1) {
                mode = 'decrease';
            }
        } else {
            // 当curr到达0时，切换模式
            curr--;
            if (curr < 1) {
                mode = 'increase';
            }
        }
    }
    // 将memo中的字符拼接成字符串
    return memo.reduce((prv, cur) => {
        return prv + cur.join('');
    }, '');
};

7.整数反转 medium

Link

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

/**
 * @param {number} x
 * @return {number}
 *
 * 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
 *
 * 如果反转后整数超过 32 位的有符号整数的范围 `[−2^31,  2^31 − 1]` ，就返回 0。
 *
 * 假设环境不允许存储 64 位整数（有符号或无符号）。
 */
const max = Math.pow(2, 31) - 1;
const min = -Math.pow(2, 31);
console.log(max, min); // 2147483647 -2147483648
// -123 => -321
var reverse = function(x) {
    const isN = x < 0;
    x = isN ? -x : x;
    let r = 0;
    while (x > 0) {
        const last = x % 10;
        x = Math.trunc(x / 10);
        if (r > 214748364) return 0;
        const maxLast = isN ? 8 : 7;
        if (r === 214748364 && last > maxLast) return 0;
        r = r * 10 + last;
    }
    return isN ? -r : r;
};

8.字符串转换整数 (atoi) medium

/**
 * @param {string} s
 * @return {number}
 *
 * 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
 *
 * 函数 myAtoi(string s) 的算法如下：
 *
 * 1. 读入字符串并丢弃无用的前导空格
 * 2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
 * 3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
 * 4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
 * 5. 如果整数数超过 32 位有符号整数范围 `[−2^31,  2^31 − 1]` ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
 * 返回整数作为最终结果。
 * 注意：
 *
 * 本题中的空白字符只包括空格字符 ' ' 。
 * 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
 */
const max = 2147483647;  // 2^31 - 1
const min = -2147483648;  // -2^31
var myAtoi = function(s) {
    s = s.trim();
    let r = 0;
    let isN = undefined;
    const numRegx = /[0-9]/;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (isN === undefined) {
            if (c === '+') {
                isN = false;
            } else if (c === '-') {
                isN = true;
            } else if (numRegx.test(c)) {
                isN = false;
                r = r * 10 + (+c);
            } else {
                break;
            }
        } else if (numRegx.test(c)) {
            r = r * 10 + (+c);
        } else {
            break;
        }
    }
    r = isN ? -r : r;
    if (r > max) return max;
    if (r < min) return min;
    return r;
};

9.回文数 easy

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数

是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

queue.js

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0) return false;
    const q = [];
    while (x > 0) {
        const last = x % 10;
        x = Math.trunc(x / 10);
        q.push(last);
    }
    while (q.length > 1) {
        const start = q.shift();
        const end = q.pop();
        if (start !== end) {
            return false;
        }
    }
    return true;
};

half.js

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0 || x % 10 === 0 && x !== 0) return false;
    let rv = 0;
    //  12`21` => 12`12`  // 12321
    while (x > rv) {
        rv = rv * 10 + x % 10;
        x = Math.trunc(x / 10);
        // last rv = 123, x = 12
    }
    return x === rv || x === Math.trunc(rv / 10);
};

console.log(isPalindrome(12321));

10.正则表达式匹配 hard

Link

11.盛最多水的容器 medium

Link

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    const n = height.length
    let max = 0
    let l = 0
    let r = n - 1
    while (l < r) {
        const d = r - l
        const hl = height[l]
        const hr = height[r]
        // 谁小移动谁
        if (hl <= hr) {
            l++
        } else {
            r--
        }
        const s = Math.min(hl, hr) * d
        max = max > s ? max : s
    }
    return max
};

12.整数转罗马数字 medium

Link

/**
 * @param {number} num
 * @return {string}
 */
// 利用减法规则 从大到小 依次减去 
var intToRoman = function(num) {
    const romanMap = [
        { value: 1000, symbol: 'M' }, { value: 900, symbol: 'CM' }, { value: 500, symbol: 'D' }, { value: 400, symbol: 'CD' }, 
        { value: 100, symbol: 'C' }, { value: 90, symbol: 'XC' }, { value: 50, symbol: 'L' }, { value: 40, symbol: 'XL' }, 
        { value: 10, symbol: 'X' }, { value: 9, symbol: 'IX' }, { value: 5, symbol: 'V' }, { value: 4, symbol: 'IV' },
        { value: 1, symbol: 'I' },
    ];
    let r = '';
    for (const { value, symbol } of romanMap) {
        while (num >= value) {
            r += symbol;
            num -= value;
        }
    }
    return r;
};

13.罗马数字转整数 easy

Link

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
    const map = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
    let sum = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        const last = s[i];
        const pre = i - 1 >= 0 ? s[i - 1] : null;
        if (pre) {
            if (map[pre] >= map[last]) {
                sum += map[last];
            } else {
                // 减去前一个 并且i--  pre被处理了 所以i--
                sum += map[last] - map[pre];
                i--;
            }
        } else {
            sum += map[last];
        }
    }
    return sum;
};

14.最长公共前缀 easy

Link

map.js

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    const map = [];
    for (let i = 0; i < strs.length; i++) {
        const s = strs[i];
        for (let j = 0; j < s.length; j++) {
            const char = s[j];
            if (!map[j]) {
                map[j] = {
                    char: char, num: 1,
                };
            } else {
                const h = map[j];
                if (h.char === char) {
                    h.num += 1;
                }
            }
        }
    }

    let r = '';

    for (let i = 0; i < map.length; i++) {
        const c = map[i];
        if (c.num === strs.length) {
            r += c.char;
        } else {
            break;
        }
    }
    return r;
};

for.js

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    let ans = strs[0]
    let r = ''
    for (let i = 0; i < ans.length; i++) {
        let pass = true
        for (let j = 1; j < strs.length; j++) {
            if (!strs[j][i] || strs[j][i] !== ans[i]) {
                pass = false
                return r
            }
        }
        if (pass) {
            r += ans[i]
        }
    }
    return r
};

15.三数之和 medium

Link

双指针法

关键字：不可以包含重复

• 利用排序避免重复答案
• 降低复杂度变成twoSum
• 利用双指针找到所有解

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSum = function (nums, target) {
    const result = [];

    if (!nums) return result;
    // arr sort 利用排序避免重复答案
    nums.sort((a, b) => a - b);

    for (let k = 0; k < nums.length; k++) {
        const target = nums[k];
        if (target > 0) break;
        // 去掉最开始已经添加过的
        if (k > 0 && nums[k] === nums[k - 1]) continue;
        let l = k + 1, r = nums.length - 1;
        // 双指针找到目标值 -nums[k]
        while (l < r) {
            const sum = nums[l] + nums[r] + target
            if (sum === 0) {
                result.push([nums[k], nums[l], nums[r]]);
                // 添加结果之后继续向内寻找 并跳过 相同的数
                while (l < r && nums[r] === nums[--r]);
                while (l < r && nums[l] === nums[++l]);
            } else if (sum > 0) {
                r--
            } else {
                l++
            }
        }
    }
    return result;
};

16.最接近的三数之和 medium

Link

var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);
    let minSum = Infinity;

    outer:
        for (let k = 0; k < nums.length; k++) {
            if (k > 0 && nums[k] === nums[k - 1]) continue;
            let l = k + 1, r = nums.length - 1;
            while (l < r) {
                const sum = nums[k] + nums[l] + nums[r];
                if (Math.abs(sum - target) < Math.abs(minSum - target)) {
                    minSum = sum;
                }
                // 等于意味着找到最小到一个 所以跳出循环
                if (sum === target) {
                    break outer;
                } else if (sum > target) {
                    r--;
                } else {
                    l++;
                }
            }

        }
    return minSum;
};

17.电话号码的字母组合 medium

Link

recusive.js

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if(!digits) return []
    const map = {
        2: 'a,b,c',
        3: 'd,e,f',
        4: 'g,h,i',
        5: 'j,k,l',
        6: 'm,n,o',
        7: 'p,q,r,s',
        8: 't,u,v',
        9: 'w,x,y,z',
    };
    const le = [];
    for (let i = 0; i < digits.length; i++) {
        le.push(map[digits[i]].split(','));
    }
    const res = [];
    function travers(remains, upLetter) {
        if (remains.length > 0) {
            const c = remains.shift();
            for (let i = 0; i < c.length; i++) {
                travers([...remains], upLetter + c[i]);
            }
        } else {
            res.push(upLetter);
        }
    }
    travers(le, '');
    return res;
};

queue.js

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    if (!digits) return []
    const map = {
        2: 'a,b,c',
        3: 'd,e,f',
        4: 'g,h,i',
        5: 'j,k,l',
        6: 'm,n,o',
        7: 'p,q,r,s',
        8: 't,u,v',
        9: 'w,x,y,z',
    };
    const le = [];
    for (let i = 0; i < digits.length; i++) {
        le.push(map[digits[i]].split(','));
    }
    const q = [''];

    for (let i = 0; i < le.length; i++) {
        const c = le[i];
        const l = q.length
        for (let j = 0; j < l; j++) {
            const temp = q.shift();
            for (let k = 0; k < c.length; k++) {
                q.push(temp + c[k]);
            }
        }
    }
    return q;
};

18.四数之和 medium

Link